package org.example.leetcode;

/**
 * @author: lynn
 * @Descript:
 * @date: 2021/8/5 12:26
 * @version: 1.0
 */
public class LC50_1 {
    public static void main(String[] args) {
        LC50_1 lc=new LC50_1();
        System.out.println(lc.myPow(
                3,5));
    }

    //fixme https://www.bilibili.com/video/BV1Qf4y1m7Uj?from=search&seid=9938879958686775622

    /**
     *  1. n>=0
     *      1.1 n%2==1, f(x,n)=f(x,n/2)*x*f(x,n/2);
     *      1.2 n%2==0, f(x,n)=f(x,n/2)*f(x,n/2);
     *      1.3 base case n=0,f(x,0)=1;
     *  2. n<0;
     */

    public double myPow(double x, int n) {
        long N=(long) n;
        if (n<0){
            N=-N;
            x=1/x;
        }
        return  pow(x, N);
    }
    private double pow(double x,long N){
        if (N==0) return 1;

        double res=pow(x,N/2);
        if (N%2==1) {
            return res*x*res;
        }else {
            return res*res;
        }
    }
}
